package com.myjavalab.exercise;

/**
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，
 * 
 * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 
 * 例如下面的二维数组就是每行、每列都递增排序。
 * 如果在这个数组中查找数字7，则返回true；如果查找数字5，
 * 由于数组不含有该数字，则返回false。
 * 
 * 	1	2	8	9
 * 	2	4	9	12
 * 	4	7	10	13
 * 	6	8	11	15
 * 
 * @author Andy.Rong
 * 
 */
public class SearchNumber {

	public static void main(String[] args) {
		int[][] array = {{1,2,8,9},{2,4,9,12}, {4,7,10,13}, {6,8,11,15}};
		if(isNumberExist(0,0,array, 5))
			System.out.println("The Number is existed");
		else 
			System.out.println("The Number is not existed");
	}
	
	public static boolean isNumberExist(int row, int column, int[][] array, int targetNumber) {
		if(array[row][column] == targetNumber) 
			return true;
		else if(array[row][column] < targetNumber && row < array.length)
			return isNumberExist(row+1, column+1, array, targetNumber);
		else {
			if(array[row-1][column] == targetNumber)
				return true;
			if(array[row][column-1] == targetNumber)
				return true;
		}
		return false;
	}
}
